package org.cabbage.lintcode;

/**
 * 计算数字k在0到n中的出现的次数，k可能是0~9的一个值
 * 例如n=12，k=1，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，我们发现1出现了5次 (1, 10, 11, 12)
 *
 * @author gezhangyuan
 */
public class Times {

    public static void main(String[] args) {
        System.out.println(digitCounts(0, 19));
    }

    public static int digitCounts(int k, int n) {
        if (k == 0 && n == 0) {
            return 1;
        }
        int length = String.valueOf(n).length();
        int sum = 0;
        for (int i = 1; i <= length; i++) {
            int temp = (int) Math.pow(10, i - 1);
            sum = sum + n / temp * (temp / 10);
            int right = Integer.valueOf(String.valueOf(n).substring(length - i, length));
            if (k != 0 || i != length) {
                if (right >= (k + 1) * temp) {
                    sum = sum + temp;
                }
                if (right >= k * temp && right < (k + 1) * temp) {
                    sum = sum + (right - k * temp + 1);
                }
            }

        }
        return sum;
    }
}
